package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//[22]括号生成
public class GenerateParentheses22 {
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses22().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            ArrayList<String> res = new ArrayList<>();
            if (n <= 0) return res;

            int l = 0, r = 0;
            gen(res, "", l, r, n);
            return res;
        }

        public void gen(List<String> res, String curStr, int l, int r, int n) {
            if (curStr.length()==2*n){
                res.add(curStr);
                return;
            }
            if (l<n){
                gen(res,curStr+"(",l+1,r,n);
            }
            if (l>r){
                gen(res,curStr+")",l,r+1,n);
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}